package com.ma.graph;

/*
    输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
    输出：false
    解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
 */
public class Solution785 {
    //记录是否时二分图
    boolean ok = true;
    //记录是否被访问过
    boolean[] isVisited;
    //给节点赋颜色，true false 两种颜色
    boolean[] color;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        isVisited = new boolean[n];
        color = new boolean[n];
        for (int i = 0; i < n; i++) {
            //if (!isVisited[i]) {
                traverse(graph, i);
            //}
        }
        return ok;
    }

    private void traverse(int[][] graph, int v) {
        if (!ok) {
            return;
        }
        isVisited[v] = true;
        for (int w : graph[v]) {
            if (!isVisited[w]) {
                color[w] = !color[v];
                traverse(graph, w);

            } else {
                if (color[w] == color[v]) {
                    ok = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution785 solution785 = new Solution785();
        /*
              输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
              输出：false
              输入：graph = [[1,3],[0,2],[1,3],[0,2]]
              输出：true
         */
        //int[][] graph = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
        //boolean bipartite = solution785.isBipartite(graph);
        //System.out.println(bipartite);
        int[][] graph1 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
        System.out.println(solution785.isBipartite(graph1));
    }


}
